


class NodeFactory:
    @classmethod
    def generateNode(cls, class_name,x):
        return class_name(x)

    @classmethod
    def generateNodes(cls, class_name, sequence):
        for seq in sequence:
            yield class_name(seq)

class SingleNode:
    def __init__(self, x):
        self.element = x
        self.next = None

class DoubleNode:
    def __init__(self, x):
        self.element = x
        self.next = None
        self.pre = None

class SingleLinkedList:
    def __init__(self, node:SingleNode):
        self.head = node

    def append(self, new_node:SingleNode):
        node = self.head

        while node.next is not None:
            node = node.next
        node.next = new_node


    def iterNodes(self):
        node = self.head
        while node is not None:
            print(node.element,sep=' ')
            node = node.next


class DoubleLinkedList:
    def __init__(self, node:DoubleNode):
        self.head = node
        self.length = 1

    def append(self, new_node:DoubleNode):
        node = self.head
        while node.next is not None:
            node = node.next
        node.next = new_node
        new_node.pre = node
        self.length += 1

    def __len__(self):
        return self.length

    def pop(self):
        node = self.head
        while node.next is not None:
            node = node.next
        node.pre.next = None
        return node.element

    def insert(self, index, new_node:DoubleNode):
        if index < 0:
            raise IndexError("index should not less than 0")
        if index == 0:
            self.head.pre = new_node
            new_node.next = self.head
            self.head = new_node
            self.length += 1
            return None
        if index >= len(self):
            node = self.head
            while node.next is not None:
                node = node.next
            node.next = new_node
            new_node.pre = node
            self.length += 1
            return None
        node = self.head
        for _ in range(index):
            node = node.next
        new_node.pre = node.pre
        node.pre = new_node
        new_node.next = node
        new_node.pre.next = new_node
        return None

    def remove(self, index):
        pass

    def iterNodes(self):
        node = self.head
        while node is not None:
            print(node.element,end=' ')
            node = node.next


# linkedList = SingleLinkedList(SingleNode(0))
# for e in NodeFactory.generateNodes(SingleNode, range(5)):
#     linkedList.append(e)
# linkedList.iterNodes()

doubleLinkedList = DoubleLinkedList(DoubleNode(0))
for e in NodeFactory.generateNodes(DoubleNode, range(1,5)):
    doubleLinkedList.append(e)
doubleLinkedList.iterNodes()
doubleLinkedList.insert(7,DoubleNode(8))
doubleLinkedList.iterNodes()